package org.ala.everyday;

import java.util.stream.IntStream;

/**
 * 给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。
 *
 * 给你一个整数 capacity ，表示每辆公交车 最多 能容纳的乘客数目。
 *
 * 每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x  且公交没有满，那么你可以搭乘这一辆公交。最早 到达的乘客优先上车。
 *
 * 返回你可以搭乘公交车的最晚到达公交站时间。你 不能 跟别的乘客同时刻到达。
 *
 * 注意：数组 buses 和 passengers 不一定是有序的。
 *
 *
 *
 * 示例 1：
 *
 * 输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2
 * 输出：16
 * 解释：
 * 第 1 辆公交车载着第 1 位乘客。
 * 第 2 辆公交车载着你和第 2 位乘客。
 * 注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。
 * 示例 2：
 *
 * 输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
 * 输出：20
 * 解释：
 * 第 1 辆公交车载着第 4 位乘客。
 * 第 2 辆公交车载着第 6 位和第 2 位乘客。
 * 第 3 辆公交车载着第 1 位乘客和你。
 *
 *
 * 提示：
 *
 * n == buses.length
 * m == passengers.length
 * 1 <= n, m, capacity <= 105
 * 2 <= buses[i], passengers[i] <= 109
 * buses 中的元素 互不相同 。
 * passengers 中的元素 互不相同 。
 *
 * @author ala
 * @date 2024-09-18 08:39
 */
public class Q2332 {
    public static void main(String[] args) {
        Q2332 q = new Q2332();

//        int[] buses = {10,20},
//              passengers = {2,17,18,19};
//        int capacity = 2;

//        int[] buses = {20,30,10},
//              passengers = {19,13,26,4,25,11,21};
//        int capacity = 2;

//        int[] buses = {3},
//              passengers = {2, 4};
//        int capacity = 2;

//        int[] buses = {2}, passengers = {2};
//        int capacity = 2;

//        int[] buses = {2,3}, passengers = {3,2};
//        int capacity = 2;

        int[] buses = {3,4,2}, passengers = {2};
        int capacity = 3;

        System.out.println(q.latestTimeCatchTheBus(buses, passengers, capacity));
    }

    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        return V1(buses, passengers, capacity);
    }
    /**
     *  1）buses, passengers 升序
     *  2）从左往右遍历 passengers，同时维护当前等公交车的人队列 queue，和下一趟公交车的下标 bi
     *  3）如果 passengers[pi] >= buses[bi]，发车，队列出列 <= busses[bi] 的最多 capacity 个
     *  4）如果下一辆 bi 就是最后一辆车，则：
     *      如果 queue 长度已经超过 capacity，则 queue 从第 capacity 开始往左遍历第一个空位
     *      如果 queue 长度未超过 capacity，则 pi 继续往右，直到 queue 长度超过 capacity，或 passengers[pi] >= buses[bi]
     *          此时再从 queue 的 capacity 位开始往前倒，找第一个空位
     */
    protected int V1(int[] buses, int[] passengers, int capacity) {
        int[] bidx = IntStream.range(0, buses.length).boxed().sorted((i1, i2) -> buses[i1] - buses[i2]).mapToInt(i -> i.intValue()).toArray(),
              pidx = IntStream.range(0, passengers.length).boxed().sorted((i1, i2) -> passengers[i1] - passengers[i2]).mapToInt(i -> i.intValue()).toArray();

        //  等车队列
        int[] queue = new int[passengers.length];
        int ql = 0, qr = -1, qs = 0;

        //  遍历等车人
        int bi = 0, pi = 0, local = -1;
        while (buses.length > 1 && pi < pidx.length) {
            int p = passengers[pidx[pi]];
            if (p <= buses[bidx[bi]]) {
                queue[++qr] = p;
                qs++;
                pi++;
            }
            //  如果到达车站的时间已经超过出发时间，发车走人
            if (p >= buses[bidx[bi]]) {
                //  如果还没到最后一辆车，前 capacity 个上车走人
                int c = 0;
                while (qs > 0 && c < capacity) {
                    ql++;
                    qs--;
                    c++;
                }
                //  最后一辆车单独装车
                if (++bi == buses.length - 1) {break;}
            }
        }
        //  如果当前等车人不够 capacity，继续往后装满 capacity 个
        while (pi < passengers.length && qs < capacity) {
            int p = passengers[pidx[pi++]];
            if (p <= buses[bidx[bi]]) {
                qs++;
                queue[++qr] = p;
            } else {
                break;
            }
        }
        if (qs == 0) { return buses[bidx[bidx.length - 1]]; }
        //  如果人数还不够 capacity
        if (qs < capacity) {
            //  判断队尾是否等于buses[bi]，若不等于，则buses[bi]就是答案
            if (queue[qr] != buses[bidx[bi]]) {return buses[bidx[bi]];}
            //  否则从qr开始往前倒，第一个断掉的地方就是答案
            else {
                while (qr > 0 && queue[qr] - 1 == queue[qr - 1]) { qr--; }
                return queue[qr] - 1;
            }
        }
        //  如果人满了，则从 ql + capacity 的位置开始往前倒，第一个断掉的地方
        else {
            qr = ql + capacity - 1;
            while (qr > 0 && queue[qr] - 1 == queue[qr - 1]) { qr--; }
            return queue[qr] - 1;
        }
    }
}
